/*
 * Copyright (C) 2010 TTPASI, Inc. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS-IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package ttpasi.jgenere.chaocipher;

import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class SequenceFinder
{
  private final String _lt;
  private final String _rt;
  private final String _ct;
  private final String _pt;

  public SequenceFinder(String lt, String rt, String ct, String pt)
  {
    this._lt = lt;
    this._rt = rt;
    this._ct = ct;
    this._pt = pt;
  }

  public List findSequences()
  {
    List sequences = new LinkedList();

    int length = _ct.length();
    for (int i = 0; i < length; i++)
    {
      int ctLength = findSequenceLength(charSet(_lt), _ct, i);
      int ptLength = findSequenceLength(charSet(_rt), _pt, i);
      if (ctLength >= 0 && ptLength >= 0)
      {
        int maxLength = Math.max(ctLength, ptLength);
        sequences.add(new Sequence(_ct.substring(i, maxLength), _pt.substring(i, maxLength)));
      }
      else
      {
        break;
      }
    }

    return sequences;
  }

  public List findMinSequencesWithHoles(int targetHolesCount)
  {
    List sequences = new LinkedList();

    int length = _ct.length();
    for (int i = 0; i < length; i++)
    {
      int ctLength = findSequenceLength(charSet(_lt), _ct, i);
      int ptLength = findSequenceLength(charSet(_rt), _pt, i);
      if (ctLength > 0 && ptLength > 0)
      {
        int maxLength = Math.max(ctLength, ptLength);
        Sequence sequence = new Sequence(_ct.substring(i, i + maxLength), _pt.substring(i, i + maxLength));
        int currentHolesCount = new HoleFinder(sequence._ct, sequence._pt).countHoles();
        if (currentHolesCount == targetHolesCount)
        {
          sequences.add(sequence);
        }
      }
      else
      {
        break;
      }
    }

    return sequences;
  }

  public List findMaxSequencesWithHoles(int targetHolesCount)
  {
    List sequences = new LinkedList();

    int length = _ct.length();
    for (int i = 0; i < length; i++)
    {
      int ctLength = findSequenceLength(charSet(_lt), _ct, i);
      int ptLength = findSequenceLength(charSet(_rt), _pt, i);
      if (ctLength > 0 && ptLength > 0)
      {
        int maxLength = Math.max(ctLength, ptLength);
        Sequence sequence = new Sequence(_ct.substring(i, i + maxLength), _pt.substring(i, i + maxLength));
        int currentHolesCount = new HoleFinder(sequence._ct, sequence._pt).countHoles();
        if (currentHolesCount <= targetHolesCount)
        {
          // expand the sequence forward until the targetHolesCount reached,
          // and then keep expanding as far as possible and still have targetHolesCount
          for (int j = i + maxLength; j < length; j++)
          {
            while (currentHolesCount < targetHolesCount && j < length)
            {
              String currentCt = sequence._ct;
              String currentPt = sequence._pt;
              char nextCtChar = _ct.charAt(j);
              char nextPtChar = _pt.charAt(j);
              String nextCt = currentCt + nextCtChar;
              String nextPt = currentPt + nextPtChar;
              sequence = new Sequence(nextCt, nextPt);
              currentHolesCount = new HoleFinder(sequence._ct, sequence._pt).countHoles();
              j++;
            }
            Sequence nextSequence = new Sequence(sequence._ct, sequence._pt);
            int nextHolesCount = currentHolesCount;
            while (nextHolesCount <= targetHolesCount && j < length)
            {
              String currentCt = sequence._ct;
              String currentPt = sequence._pt;
              char nextCtChar = _ct.charAt(j);
              char nextPtChar = _pt.charAt(j);
              String nextCt = currentCt + nextCtChar;
              String nextPt = currentPt + nextPtChar;
              nextHolesCount = new HoleFinder(nextCt, nextPt).countHoles();
              if (nextHolesCount <= targetHolesCount)
              {
                nextSequence = new Sequence(nextCt, nextPt);
              }
              j++;
            }
            sequence = nextSequence;
          }
          if (currentHolesCount == targetHolesCount)
          {
            sequences.add(sequence);
          }
        }
      }
      else
      {
        break;
      }
    }

    return sequences;
  }

  private static int findSequenceLength(Set alphabet, String text, int start)
  {
    int count = 0;
    int length = text.length();
    for (int i = start; i < length && !alphabet.isEmpty(); i++)
    {
      count++;
      alphabet.remove(new Character(text.charAt(i)));
    }
    return alphabet.isEmpty() ? count : -1;
  }

  private static Set charSet(String alphabet)
  {
    Set chars = new TreeSet();
    char[] alphabetChars = alphabet.toCharArray();
    for (int i = 0; i < alphabetChars.length; i++)
    {
      chars.add(new Character(alphabetChars[i]));
    }
    return chars;
  }

  public static final class Sequence
  {
    public final String _ct;
    public final String _pt;

    Sequence(String ct, String pt)
    {
      this._ct = ct;
      this._pt = pt;
    }
  }
}
